#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 1e4 + 10;

int n, k;
LL c[N], v[N], tmp[N];

bool check(int x)
{
	for(int i = 1; i <= n; i++)
	{
		tmp[i] = v[i] - x * c[i];
	}
	sort(tmp + 1, tmp + 1 + n);
	
	LL sum = 0;
	for(int i = n; i >= n - k + 1; i--) sum += tmp[i];
	
	return sum >= 0; 
}

int main()
{
	int T; cin >> T;
	while(T--)
	{
		cin >> n >> k;
		for(int i = 1; i <= n; i++) cin >> c[i] >> v[i];
		
		int l = 0, r = 1e4;
		while(l < r)
		{
			int mid = (l + r + 1) / 2;
			if(check(mid)) l = mid;
			else r = mid - 1;
		}
		cout << r << endl;
	} 
	
	return 0;
} 














